#include "main.h"
void _recur_create_tree(BiTreeNode* root_pp, char* pre_order_seq, int* current_index, int num_elements) {
    if (*current_index >= num_elements) {
        return;
    }
    else {
        root_pp->data = pre_order_seq[*current_index];
        *current_index += 1;
    }
    if (pre_order_seq[*current_index] == '#') {
        root_pp->leftChild = NULL;
        *current_index += 1;
    }
    else {
        root_pp->leftChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _recur_create_tree(root_pp->leftChild, pre_order_seq, current_index, num_elements);
    }
    if (pre_order_seq[*current_index] == '#') {
        root_pp->rightChild = NULL;
        *current_index += 1;
    }
    else {
        root_pp->rightChild = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        _recur_create_tree(root_pp->rightChild, pre_order_seq, current_index, num_elements);
    }
}


void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
    *root_pp = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    BiTreeNode* root = *root_pp;
    if (pre_order_seq[0] != '#') {
        root->data = pre_order_seq[0];
    }
    int current_index = 0;
    _recur_create_tree(*root_pp, pre_order_seq, &current_index, num_elements);
}
void pre_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }
}
void in_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t == NULL) {
        return;
    }
    in_order_traverse(t->leftChild, visit);
    visit(t->data);
    in_order_traverse(t->rightChild, visit);
}
void post_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t == NULL) {
        return;
    }
    post_order_traverse(t->leftChild, visit);
    post_order_traverse(t->rightChild, visit);
    visit(t->data);
}
void visit(DataType item) {
    printf("%c ", item);
}
BiTreeNode* search(BiTreeNode* root, DataType x) {
    BiTreeNode* find = NULL;
    if (root == NULL) {
        return NULL;
    }
    if (root->data == x) {
        return root;
    }
    else {
        find = search(root->leftChild, x);
        if (find) {
            return find;
        }
        find = search(root->rightChild, x);
        if (find) {
            return find;
        }
    }
    return find;
}
void destroy(BiTreeNode** root) {
    if ((*root) != NULL) {
        if ((*root)->leftChild) {
            destroy(&(*root)->leftChild);
            (*root)->leftChild = NULL;
        }
        if ((*root)->rightChild) {
            destroy(&(*root)->rightChild);
            (*root)->rightChild = NULL;
        }
        if ((*root) != NULL) {
            free((*root));
            (*root) = NULL;
        }
    }
}
int main() {
    BiTreeNode* root;
    char x = 'A';
    char* pre_order_seq = "ABC##DE#G##F###";
    create_tree(&root, pre_order_seq, 15);
    printf("前序遍历为：");
    pre_order_traverse(root, visit);
    printf("\n中序遍历为：");
    in_order_traverse(root, visit);
    printf("\n后序遍历为：");
    post_order_traverse(root, visit);
    search(root, x);
    printf("\n数据元素%c在二叉树中 \n", x);
    destroy(&root);
}